package Leetcode.树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import static Leetcode.树.TreeNode.arrayToTree;

/**
 * @ClassName 最大层内元素和
 * @since: 2023/8/20 09:16
 * @auth: kirito
 * @description:
 * 给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
 *
 * 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
 *
 * 在初始化变量 max 时，直接使用了 root.val，
 * 但是在判断 root 是否为空之前，会导致空指针异常。
 * 应该将初始化 max 的代码放在判断 root 是否为空之后。
 *
 *
 **/
public class 最大层内元素和 {
    public static int maxLevelSum(TreeNode root) {
// * 在初始化变量 max 时，直接使用了 root.val，
// * 但是在判断 root 是否为空之前，会导致空指针异常。
// * 应该将初始化 max 的代码放在判断 root 是否为空之后。
        if (root == null) {
            return 0;
        }

        int max = root.val; // 保存最大层级和的值
        int depth = 1; // 当前层级
        int ans = 1; // 最大层级和所在的层级

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
//            在内层循环中，使用 queue.size() 作为循环的终止条件，
//            但是在循环过程中，队列的大小是会动态变化的，因此不能使用固定的大小。
//            应该在每一层开始之前，先将当前层的节点个数保存下来，
//            然后在循环中使用这个固定的节点个数作为终止条件。
            int size = queue.size(); // 当前层级的节点个数
            int sum = 0; // 当前层级的节点值之和

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;

                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }

            if (sum > max) {
                max = sum; // 更新最大层级和
                ans = depth; // 更新最大层级和所在的层级
            }

            depth++; // 进入下一层级
        }

        return ans; // 返回最大层级和所在的层级
    }
    public static void main(String[] args) {
        // 创建二叉树的数组表示
        Integer[] arr = {989, null, 10250, 98693, -89388, null, null, null, -32127};

        // 将数组转换为二叉树
        TreeNode root = arrayToTree(arr);

        int result = maxLevelSum(root);

        System.out.println(result);
    }
}
